#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>

using namespace std;

namespace lh
{

    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}   
        TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    };

	//Leetcode-107. 二叉树的层序遍历 II
	//https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            queue<TreeNode*>q;
            size_t levelSize = 0;//记录每层的数据个数
            if (root)
            {
                q.push(root);
                levelSize = 1;
            }
            vector<vector<int>>res;
            while (!q.empty())
            {
                vector<int>v;
                for (int i = 0; i < levelSize; i++)
                {
                    TreeNode* front = q.front();
                    q.pop();
                    v.push_back(front->val);
                    if (front->left)
                        q.push(front->left);
                    if (front->right)
                        q.push(front->right);
                }
                res.push_back(v);
                //当前层出完，下一层都进了队列，队列的size就是下一层的数据个数。
                levelSize = q.size();
            }
            reverse(res.begin(), res.end());
            return res;
        }
    };

    //Leetcode-606. 根据二叉树创建字符串
    //https://leetcode.cn/problems/construct-string-from-binary-tree/
    class Solution2 {
    public:
        string tree2str(TreeNode* root) {
            //1.左右都为空，括号省略
            //2.左不为空，右为空，左部括号不省略，右边省略
            //3.左为空，右不为空，左部括号不省略
            if (root == nullptr)
                return string();
            string str;
            str += to_string(root->val);


            //左边不为空，或者左部为空了右部不为空，左部加括号
            if (root->left || root->right)
            {
                str += '(';
                str += tree2str(root->left);
                str += ')';
            }


            //右边不为空，右边需要加括号
            if (root->right)
            {
                str += '(';
                str += tree2str(root->right);
                str += ')';
            }
            return str;
        }
    };


    //Leetcode-236. 二叉树的最近公共祖先
    //https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 // class Solution3 {
 // public:
 //     bool FindR(TreeNode* sub,TreeNode* x)
 //     {
 //         //递归查找
 //         if(sub==nullptr)
 //             return false;
 //         return sub==x
 //             || FindR(sub->left,x)
 //             || FindR(sub->right,x);
 //     }
 //     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
 //         //1.如果一个在左子树，一个在右子树，那么当前root就是最近公共祖先
 //         //2.如果其中一个就是root，那么当前root本身就是最近公共祖先
 //         //3.如果在同一侧，则递归进入同一侧子树寻找
 //         if(root==nullptr)
 //             return nullptr;
 //         //如果是其中一个，就是root本身
 //         if(root==p||root==q)
 //             return root;

 //         bool pInLeft,pInRight,qInLeft,qInRight;
 //         pInLeft=FindR(root->left,p);
 //         //互斥，不是在左就是在右
 //         pInRight=!pInLeft;

 //         qInLeft=FindR(root->left,q);
 //         qInRight=!qInLeft;

 //         //一个在左，一个在右，则是root本身
 //         if((pInLeft&&qInRight)||(pInRight&&qInLeft))
 //         {
 //             return root;
 //         }
 //         else if(pInLeft&&qInLeft)
 //         {
 //             return lowestCommonAncestor(root->left,p,q);
 //         }
 //         else if(pInRight&&qInRight)
 //         {
 //             return lowestCommonAncestor(root->right,p,q);
 //         }
 //         else
 //         {
 //             return nullptr;
 //         }

 //     }
 // };
    class Solution3 {
    public:
        bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
        {
            //求路径
            if (root == nullptr)
                return false;
            //直接入栈，下面判断是否是路径
            path.push(root);
            if (root == x)
                return true;
            if (FindPath(root->left, x, path))
                return true;
            if (FindPath(root->right, x, path))
                return true;
            //如果都没找到出栈，该结点不是路径
            path.pop();
            return false;
        }

        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            stack<TreeNode*>pPath, qPath;
            FindPath(root, p, pPath);
            FindPath(root, q, qPath);

            //找到了路径，链表相交问题
            while (pPath.size() != qPath.size())
            {
                if (pPath.size() > qPath.size())
                    pPath.pop();
                else
                    qPath.pop();
            }

            while (pPath.top() != qPath.top())
            {
                pPath.pop();
                qPath.pop();
            }
            return pPath.top();
        }
    };


    //JZ36 二叉搜索树与双向链表
    //https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&ru=/exam/oj
    class Solution4 {
    public:
        //left指向中序的前一个
        //right指向中序的后一个
        void InOrderConvert(TreeNode* cur, TreeNode*& prev)
        {
            if (cur == nullptr)
                return;
            InOrderConvert(cur->left, prev);
            cur->left = prev;
            //穿越回上一个，告诉上一个的right是什么，此时的prev上一个也就是上一个的cur
            if (prev)
                prev->right = cur;
            //往后走
            prev = cur;
            InOrderConvert(cur->right, prev);
        }
        TreeNode* Convert(TreeNode* pRootOfTree) {
            TreeNode* prev = nullptr;
            InOrderConvert(pRootOfTree, prev);

            //找到头
            TreeNode* head = pRootOfTree;
            while (head && head->left)
            {
                head = head->left;
            }
            return head;
        }
    };


    //105. 从前序与中序遍历序列构造二叉树
    //https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
    class Solution5 {
    public:
        //前序找根创建结点，中序划分左右子树
        TreeNode* _bulidTree(vector<int>& preorder, vector<int>& inorder, int& previ, int inbegin, int inend)
        {
            if (inbegin > inend)
            {
                return nullptr;
            }
            TreeNode* root = new TreeNode(preorder[previ++]);
            //分割中序
            int ini = inbegin;
            while (ini <= inend)
            {
                if (inorder[ini] == root->val)
                    break;
                else
                    ++ini;
            }
            //[inbegin,ini-1] ini [ini+1,inend]
            root->left = _bulidTree(preorder, inorder, previ, inbegin, ini - 1);
            root->right = _bulidTree(preorder, inorder, previ, ini + 1, inend);
            return root;
        }

        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int i = 0;
            return _bulidTree(preorder, inorder, i, 0, inorder.size() - 1);
        }
    };

}

int main()
{
	return 0;
}